package com.skh.array;


import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 求众数(多数元素)
 * created by skh on 2018/8/19
 */
public class MajorityElement {

	/*
	给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

	你可以假设数组是非空的，并且给定的数组总是存在众数。

	示例 1:

	输入: [3,2,3]
	输出: 3
	示例 2:

	输入: [2,2,1,1,1,2,2]
	输出: 2
	 */

	/*
	摩尔投票法 Moore Voting，需要O(n)的时间和O(1)的空间
	这种投票法先将第一个数字假设为众数，然后把计数器设为1，比较下一个数和此数是否相等，若相等则计数器加一，反之减一。
	然后看此时计数器的值，若为零，则将当前值设为候选众数。以此类推直到遍历完整个数组，当前候选众数即为该数组的众数
	 */
	public int majorityElement(int[] nums) {
		Integer num = null; //众数
		int count = 0;
		for (int i=0;i<nums.length;i++) {
			if (count == 0) {
				num = nums[i];
				count++;
			}else {
				if (nums[i] == num) {
					count++;
				} else {
					count--;
				}
			}
		}

		return num;
	}

	/*
	利用HashMap数据结构，其中key值存数组中的值，value值存出现的次数，每存一个数判断一下是不是次数大于n/2了，如果是就说明找到了，就返回，不是就把次数加1，继续找。
	 */
	public int majorityElement2(int[] nums) {
		Map<Integer, Integer> map = new HashMap<>();

		for (int i=0;i<nums.length;i++) {
			int num = nums[i];
			if (map.containsKey(num)){
				Integer count = map.get(num);
				count++;
				map.put(num, count);
			}else {
				map.put(num,1);
			}

			if (map.get(num) > nums.length / 2) {
				return num;
			}

		}
		return 0;
	}

	/**
	 * 因为大于一半, 所以排序后的 中间那个数必是
	 * @param nums
	 * @return
	 */
	public int majorityElement3(int[] nums) {
		Arrays.sort(nums);
		return nums[nums.length / 2];
	}
}
